1. Field of the Invention
The present invention relates to a method of generating two-dimensional images of three-dimensional solid objects in a graphics processing system and to a graphics processing system for performing such a method.
Objects may be represented in a graphics processing system using various techniques. One which is particularly suitable for representing solid objects is "Constructive Solid Geometry" (CSG). In accordance with this technique a three-dimensional (3-D) solid object is represented by a functional definition identifying the set of points which lie within the object. Typically, the object is defined by a Boolean function which returns a "true" if applied to a point within the object and returns a "false" otherwise. This technique contrasts with, for example, line drawing techniques where the edges and surfaces of an object are defined rather than its volume.
The functional definition or representation of an object effectively defines the set of points which make up the object. The functional definition of a sphere, for example, defines the set of points lying within a given radius of a center point. Composite objects are defined by combining the functional definitions of constituent basic objects, or "primitives", e.g. spheres, infinite planes, infinite cylinders. The functional definition of a dumb-bell, for example, comprises the functional definition of each of two spheres at different positions, the functional definition of an infinite cylinder whose axis passes through the centers of the spheres, and the functional definition of two planar half-spaces which truncate the cylinder at the spheres. The functional definitions of the spheres, the cylinder and the half-spaces are combined using combinational operators such as the set union and intersection operators (i.e. using set theory principles). Primitives can also be combined using set subtracting operators to define, for example, a composite object with a cut-out or hole. In this way hollow composite objects can be defined by subtracting a smaller object from a larger one. Such composite objects are still "solid" within the meaning of this document because the individual object definitions which make up the composite object are solid.
A composite object formed from primitives can be structured in a number of ways. However it is usual to use a tree structure with the composite object defined at the root of the tree, the primitives defined at the leaves and operators defining the combinational operations to be performed to construct the object from the primitives stored at nodes in the tree.
The range of shapes which can be defined in this way is, in practice, dependent on the set of primitives chosen. In many prior systems, objects are constructed only from planar half-spaces. A planar half-space is a functional definition of an infinite object which exists on one side of a plane. The functional definition of a cube is, for example, defined by combining the functional definitions of six half-spaces using the set intersection operator. Other systems have also been implemented using cylinders, spheres, tori, ellipsoids and even helices.
2. Description of the Prior Art
The standard technique for generating a two-dimensional (2-D) image of a transform of a three-dimensional (3-D) solid object (e.g. a 2-D perspective image of the object) is to transform the object so as to correspond with the perspective i.e., the objects are made relatively larger at the front and smaller at the back. In other words, the object is transformed from the space in which it exists (world-space) into perspective viewing space by subjecting it to a perspective transform algorithm. Then, in perspective viewing space, tests are performed to see which surfaces are at the front of the object and these are represented on the 2-D perspective image. It is usual to use a technique called spatial sub-division.
This approach was adopted by Woodwark and Quinlan in their paper entitled "Reducing the effect of complexity on volume model evaluation" published in March 1982 in Computer Design, Vol 14, No. 2.
Their method of producing a 2-D perspective view of a 3-D solid object, which employs spatial sub-division, can be summarised as follows:
The object in question is transformed into perspective space. This perspective representation of the object is then enclosed in a three-dimensional rectangular box. A test is made to find whether the box intersects this object. If it does the box is subdivided into eight equal sub-boxes, dividing each square face into four smaller rectangles. These smaller rectangular boxes are then tested in turn and any of which are empty are discarded. Those which contain part of the object are kept and subdivided again and the process is repeated until the rectangular boxes are sufficiently small to correspond with single screen pixels. These pixels are then coloured appropriately on the screen.
This prior method works well in principle, as long as the object can be easily transformed into perspective space--if the object has, for example, flat surfaces. In the case of objects such as conical, spherical or cylindrical surfaces, the functional definitions of the object in perspective space rapidly become so complex as to be impractical to manage using the prior approach, especially in the case of composite objects (e.g. complex molecules) which are made up of many such shapes.